Write a function:
def solution(A)
that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.
For example, given array A such that: A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9
the function should return 7, as explained in the example above.
Assume that:
N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Creating sample Array
In [3]:
A = [9,3,9,3,9,7,9]
In [4]:
print len(A)
In [8]:
print sorted(A)
designing algorithm
In [31]:
single_num = sorted(A)[0]
count = 0
if len(A) == 0:
print A
for num in sorted(A):
print "num: ", num
if num % single_num:
print "single num: ", single_num
print "count: ", count
if count > 1:
single_num = num
count = 0
else:
print single_num
break
count += 1
#print single_num
In [63]:
def solution_1(A):
if len(A) == 0:
return A
elif len(A) == 1:
return A[0]
elif type(A) is int:
return A
elif len(A) % 2:
single_num = sorted(A)[0]
count = 0
for i,num in enumerate(sorted(A)):
if num != single_num:
print "num: ", num
print "single num: ", single_num
print "Count: ", count
if count > 1:
single_num = num
count = 1
elif count == 1:
return single_num
else:
count += 1
if i >= len(A)-1:
return single_num
print "end single num: ", single_num
print "end count: ", count
print "end num: ", num
In [64]:
print sorted(A), "\n"
print solution(A)
In [65]:
B = [2, 2, 3, 3, 4]
In [66]:
print sorted(B), "\n"
print solution(B)
version 2-
In [82]:
def solution_2(A):
if len(A) == 0:
return A
elif len(A) == 1:
return A[0]
elif type(A) is int:
return A
elif len(A) % 2:
single_num = sorted(A)[0]
count = 0
for i,num in enumerate(sorted(A)):
if num != single_num:
print "num: ", num
print "Count: ", count
print "single num: ", single_num
if count > 1:
single_num = num
count = 1
elif count == 1:
return str(single_num) +" " + str(sorted(A[i-5:i+5]))
else:
count += 1
if i >= len(A)-1:
return single_num
In [83]:
print sorted(B)
print solution_2(B)
In [84]:
print sorted(A)
print solution_2(A)
V3
In [ ]:
def solution_3(A):
if len(A) == 0:
return A
elif len(A) == 1:
return A[0]
elif type(A) is int:
return A
elif len(A) % 2:
single_num = sorted(A)[0]
count = 1
for i,num in enumerate(sorted(A)):
if num != single_num:
if count > 1:
single_num = num
count = 1
elif count == 1:
return single_num
else:
count += 1
if i >= len(A)-1:
return single_num
V4
In [88]:
def solution_4(A):
if len(A) == 0:
return A
elif len(A) == 1:
return A[0]
elif type(A) is int:
return A
elif len(A) % 2:
single_num = sorted(A)[0]
count = 1
for i,num in enumerate(sorted(A)):
if num != single_num:
if count > 1:
single_num = num
count = 1
elif count == 1:
return single_num
elif single_num == num:
count += 1
if i >= len(A)-1:
return single_num
In [93]:
sorted(A)
print A
print solution_4(A)
V 5 - Some where long the lines forgot about the fine line "All but one occurs Even number of times". Instead solved it for "all but one int does not have any pair, is only a single element". Fixing the solutions now.
In [103]:
def solution_5(A):
if len(A) == 0:
return A
elif len(A) == 1:
return A[0]
elif type(A) is int:
return A
elif len(A) % 2:
single_num = sorted(A)[0]
count = 0
for i,num in enumerate(sorted(A)):
if num != single_num:
if count > 1:
if count % 2:
print "count", count
print "num", num
print "single num", single_num
return single_num
single_num = num
count = 1
elif count == 1:
print "count", count
print "num", num
print "single num", single_num
return single_num
elif single_num == num:
count += 1
if i >= len(A)-1:
return single_num
In [104]:
print solution_5(A)
In [106]:
1 % 2
Out[106]:
V5 .1
In [109]:
def solution_5_1(A):
if len(A) == 0:
return A
elif len(A) == 1:
return A[0]
elif type(A) is int:
return A
elif len(A) % 2:
single_num = sorted(A)[0]
count = 0
for i,num in enumerate(sorted(A)):
if num != single_num:
if count % 2:
print "count", count
print "num", num
print "single num", single_num
return single_num
single_num = num
count = 1
elif single_num == num:
count += 1
if i >= len(A)-1:
return single_num
In [111]:
print solution_5_1(A)
V 5_2
In [113]:
def solution_5_2(A):
if len(A) == 0:
return A
elif len(A) == 1:
return A[0]
elif type(A) is int:
return A
elif len(A) % 2:
single_num = sorted(A)[0]
count = 0
for i,num in enumerate(sorted(A)):
if num != single_num:
if count % 2:
return single_num
else:
single_num = num
count = 1
elif single_num == num:
count += 1
if i >= len(A)-1:
if count % 2:
return single_num
else
#just in case-
return None
In [115]:
print solution_5_2(A)
In [ ]: